import lombok.Data;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

@Data
public class 哈夫曼加解密 {

    private HuffmanNode treeNode;

    private HuffmanNode getTreeNode() {
        return treeNode;
    }

    private void setTreeNode(HuffmanNode treeNode) {
        this.treeNode = treeNode;
    }

    @Data
    public class HuffmanNode {
        private int order;
        private String content;
        private HuffmanNode leftNode;
        private HuffmanNode rightNode;
        private HuffmanNode parentNode;
        private String code;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            HuffmanNode that = (HuffmanNode) o;
            return order == that.order;
        }

        @Override
        public int hashCode() {
            return order;
        }
    }

    public void generateTree(String string) {
        String[] str = string.split("");
        Map<String, Integer> map = new HashMap<>();
        for (String st : str) {
            int i = 1;
            if (map.get(st) != null) {
                i = map.get(st) + 1;
            }
            map.put(st, i);
        }
        generateTree(map);
    }

    public void generateTree(Map<String, Integer> map) {
        List<HuffmanNode> list = new ArrayList<>();
        HuffmanNode huffmanNode;
        for (Map.Entry<String, Integer> mp : map.entrySet()) {
            huffmanNode = new HuffmanNode();
            huffmanNode.setOrder(mp.getValue());
            huffmanNode.setContent(mp.getKey());
            list.add(huffmanNode);
        }
        generateTree(list);
    }

    /**
     * get number
     *
     * @param content
     * @return
     */
    public String queryBinary(String content) {
        StringBuilder res = new StringBuilder();
        Queue<HuffmanNode> queue = new LinkedBlockingDeque<>();
        int i = 0;
        while (i < content.length()) {
            queue.add(this.treeNode);
            while (!queue.isEmpty() && i < content.length()) {
                HuffmanNode poll = queue.poll();
                if (poll.getLeftNode() == null && poll.getRightNode() == null) {
                    if ((content.charAt(i) + "").equals(poll.getContent())) {
                        res.append(number(poll));
                        continue;
                    }
                }
                if (poll.getLeftNode() != null) {
                    queue.add(poll.getLeftNode());
                }
                if (poll.getRightNode() != null) {
                    queue.add(poll.getRightNode());
                }
            }
            i++;
        }
        return res.toString();
    }

    private String number(HuffmanNode huffmanNode) {
        StringBuilder res = new StringBuilder();
        HuffmanNode hn = huffmanNode;
        while (hn != null) {
            if (hn.getCode() != null) {
                res.append(hn.getCode());
            }
            hn = hn.getParentNode();
        }
        return res.reverse().toString();
    }

    /**
     * get content through binary
     *
     * @param binary
     * @return
     */
    public String queryContent(String binary) {
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < binary.length()) {
            HuffmanNode huffmanNode = treeNode;
            for (; i < binary.length(); i++) {
                if (binary.charAt(i) == '0') {
                    huffmanNode = huffmanNode.getLeftNode();
                } else {
                    huffmanNode = huffmanNode.getRightNode();
                }
                if (huffmanNode.getLeftNode() == null && huffmanNode.getRightNode() == null) {
                    res.append(huffmanNode.getContent());
                    i++;
                    break;
                }
            }
        }
        return res.toString();
    }

    private void generateTree(List<HuffmanNode> list) {
        PriorityQueue<HuffmanNode> lists = new PriorityQueue<>(list.size(), new Comparator<HuffmanNode>() {
            @Override
            public int compare(HuffmanNode o1, HuffmanNode o2) {
                return o1.getOrder() > o2.getOrder() ? 1 : -1;
            }
        });
        lists.addAll(list);
        while (lists.size() > 1) {
            lists.add(getNode(lists.poll(), lists.poll()));
        }
        this.treeNode = lists.poll();
    }

    private HuffmanNode getNode(HuffmanNode smaller, HuffmanNode bigger) {
        HuffmanNode huffmanNode = new HuffmanNode();
        huffmanNode.setOrder(bigger.getOrder() + smaller.getOrder());
        huffmanNode.setLeftNode(bigger);
        huffmanNode.setRightNode(smaller);
        smaller.setCode("1");
        smaller.setParentNode(huffmanNode);
        bigger.setCode("0");
        bigger.setParentNode(huffmanNode);
        return huffmanNode;
    }

    public static void main(String[] args) {
        哈夫曼加解密 哈夫曼加解密 = new 哈夫曼加解密();
        哈夫曼加解密.generateTree("2323jfdslkfajoejasfeoj");
        int total = 100000;
        long l = System.currentTimeMillis();
        String s = null;
        for (int i = 0; i < total; i++) {
            s = 哈夫曼加解密.queryBinary("2323jfdslkfajoejasfeoj");
        }
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(s);
        long x = System.currentTimeMillis();
        for (int i = 0; i < total; i++) {
            s = 哈夫曼加解密.queryContent("000010000001001101001111010010100100010001111011000011100111010100001011011");
        }
        System.out.println(System.currentTimeMillis() - x);
        System.out.println(s);
        System.out.println(哈夫曼加解密.getTreeNode().getLeftNode().getCode());
    }
}
